package class01

import "math"

/*
	给定一个二叉树的头节点head，路径的规定有以下三种不同的规定:
	1) 路径必须是头节点出发，到叶节点为止，返回最大路径和。
	2）路径可以从任何节点出发，但是必须往下走到任何节点，返回最大路径和
	3）路径可以从任何节点出发，到任何节点，返回最大路和
*/

type Node struct {
	Value int
	Left *Node
	Right *Node
}

func NewNode(value int) *Node {
	return &Node{Value:value}
}

// 1) 路径必须是头节点出发，到叶节点为止，返回最大路径和。
func GetMaxPathSum1(root *Node) int {
	var ans int
	fn := func(pathSum int) {
		ans = max(ans, pathSum)
	}
	ProcessOne(root, 0, fn)
	return ans
}

func ProcessOne(node *Node, pathSum int, fn func(int)){
	if node.Left == nil && node.Right == nil {
		fn(pathSum+node.Value)
		return
	}
	if node.Left != nil {
		ProcessOne(node.Left, pathSum+node.Value,  fn)
	}
	if node.Right != nil{
		ProcessOne(node.Right, pathSum+node.Value, fn)
	}
}

// 2）路径可以从任何节点出发，但是必须往下走到任何节点，返回最大路径和
type PathSum2Info struct {
	AllTreeMax    int
	PassMyMax     int
}

func GetMaxPathSum2(root *Node) int {
	return ProcessTwo(root).AllTreeMax
}

// 1. 与x无关：p1：左边数的最大路径和 p2：右边树的最大路径和
// 2. 与x有关：p3：x自己的值         p4：x往左走           p5: x往右走
func ProcessTwo(node *Node) *PathSum2Info {
	if node == nil {
		return nil
	}

	left := ProcessTwo(node.Left)
	right := ProcessTwo(node.Right)
	p1 := math.MinInt
	if left != nil {
		p1 = left.AllTreeMax
	}
	p2 := math.MinInt
	if right != nil {
		p2 = right.AllTreeMax
	}
	p3 := node.Value
	p4 := math.MinInt
	if left != nil {
		p4 = node.Value + left.PassMyMax
	}
	p5 := math.MinInt
	if right != nil {
		p5 = node.Value + right.PassMyMax
	}

	return &PathSum2Info{
		AllTreeMax: max(p1, max(p2, max(p3, max(p4, p5)))),
		PassMyMax: max(p3, max(p4, p5)),
	}
}

//3）路径可以从任何节点出发，到任何节点，返回最大路和
func GetMaxPathSum3(root *Node) int {
	return ProcessTwo(root).AllTreeMax
}

type PathSum3Info struct {
	AllTreeMax    int
	PassMyMax     int
}

// 1. 与x无关：p1：左边数的最大路径和 p2：右边树的最大路径和
// 2. 与x有关：p3：x自己的值         p4：x往左走           p5: x往右走  p6: x既往左，x又往右
func ProcessThree(node *Node) *PathSum3Info {
	if node == nil {
		return nil
	}
	left  := ProcessThree(node.Left)
	right := ProcessThree(node.Right)
	p1 := math.MinInt
	if left != nil {
		p1 = left.AllTreeMax
	}
	p2 := math.MinInt
	if right != nil {
		p2 = right.AllTreeMax
	}
	p3 := node.Value
	p4 := math.MinInt
	if left != nil {
		p4 = node.Value + left.PassMyMax
	}
	p5 := math.MinInt
	if right != nil {
		p4 = node.Value + right.PassMyMax
	}
	p6 := node.Value
	if right != nil {
		p6 += right.PassMyMax
	}
	if left != nil {
		p6 += left.PassMyMax
	}
	return &PathSum3Info{
		AllTreeMax: max(p1, max(p2, max(p3, max(p4, max(p5, p6))))),
		PassMyMax: max(p3, max(p4, max(p5, p6))),
	}
}